public class Sort {
    /**
     * 直接插入排序
     * @param array
     *      1.从1开始进行插入
     *      2.将i下标元素值放到tmp中
     *      3.如果tmp < array[j],交换,反之,修改ij,i++,j = i - 1
     * 时间复杂度:
     *      最好情况下:O(N)
     *      最坏情况下:O(N^2)
     * 空间复杂度:O(1)
     * 稳定性:稳定的
     * 注:不稳定的排序无法变稳定,但稳定的排序可以变的不稳定,所以直接插入排序为稳定的
     * 特点:数据越有序,排序越快
     */
    public static void insertSort(int[] array) {
        for(int i = 1;i < array.length;i++) {
            int tmp = array[i];
            int j = i - 1;
            for(;j >= 0;j--) {
                if(tmp < array[j]) {
                    array[j + 1] = array[j];
                    array[j] = tmp;
                }else {
                    break;
                }
            }
        }
    }
    /**
     * 希尔排序
     *      时间复杂度:O(N^1.25)-O(N^1.5)
     *      空间复杂度:O(N)
     *      稳定性:不稳定
     */
    public static void shellSort(int[] array) {
        int gap = array.length;
        while(gap > 0) {
            gap = gap / 2;
            shell(array,gap);
        }
    }

    /**
     * 直接插入排序
     * @param array
     * @param gap
     */
    private static void shell(int[] array,int gap) {
        for(int i = gap;i < array.length;i++) {
            int j = i - gap;
            int tmp = array[i];
            for(;j >= 0;j -= gap) {
                if(tmp < array[j]) {
                    array[j + gap] = array[j];
                }else {
                    break;
                }
            }
            array[j + gap] = tmp;
        }
    }
    /**
     * 直接选择排序
     *      时间复杂度:O(N^2)
     *      空间复杂度:O(1)
     *      稳定性:不稳定
     */
    public static void selectSort(int[] array) {
        for(int i = 0;i < array.length;i++) {
            int minIndex = i;
            for(int j = i + 1;j < array.length;j++) {
                if(array[j] < array[minIndex]) {
                    minIndex = j;
                }
            }
            swap(array,i,minIndex);
        }
    }
    private static void swap(int[] array,int i,int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }
    public static void selectSort2(int[] array) {
        int left = 0;
        int right = array.length - 1;
        while(left < right) {
            int minIndex = left;
            int maxIndex = left;
            int i = left + 1;
            while(i <= right) {
                if(array[i] < array[minIndex]) {
                    minIndex = i;
                }
                if(array[i] > array[maxIndex]) {
                    maxIndex = i;
                }
                i++;
            }
            swap(array,left,minIndex);
            if(maxIndex == left) {
                maxIndex = minIndex;
            }
            swap(array,right,maxIndex);
            left++;
            right--;
        }
    }
    /**
     * 堆排序
     *      时间复杂度:O(N * log2(为底)N)
     *      空间复杂度:O(1)
     *      稳定性:不稳定
     */
    public static void heapSort(int[] array) {
        createBigHeap(array);
        int end = array.length - 1;
        while(end > 0) {
            swap(array,0,end);
            siftDown(array,0,end);
            end--;
        }
    }
    /**
     * 创建大根堆
     */
    private static void createBigHeap(int[] array) {
        for(int i = (array.length - 1 - 1) / 2;i >= 0;i--) {
            siftDown(array,i,array.length);
        }
    }
    private static void siftDown(int[] array,int parent,int len) {
        int child = 2 * parent + 1;
        while(child < len) {
            if(child + 1 < len
                    && array[child] <  array[child + 1]) {
                child++;
            }
            if(array[child] > array[parent]) {
                swap(array,child,parent);
                parent = child;
                child = 2 * parent + 1;
            }else {
                break;
            }
        }
    }
    /**
     * 冒泡排序
     *      时间复杂度:O(N^2)
     *      空间复杂度:O(1)
     *      稳定性:稳定
     */
    public static void bubbleSort(int[] array) {
        for(int i = 0;i < array.length - 1;i++) {
            boolean flag = false;
            for(int j = 0;j < array.length - i - 1;j++) {
                if(array[j + 1] < array[j]) {
                    swap(array,j,j + 1);
                    flag = true;
                }
            }
            if(!flag) {
                break;
            }
        }
    }
}
